package leetcode.dfs;

import java.util.ArrayList;
import java.util.List;

public class Offer087 {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        //首先要判断s中是否只包含数字
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c > '9' || c < '0') return ans;
        }
        dfs(s, sb, 0, 0, ans);
        return ans;
    }

    public void dfs(String s, StringBuffer sb, int index, int site, List<String> ans) {
        int len = s.length();
        if (site == 3) {
            if (len - index > 3 || len <= index) return;
            String s3 = s.substring(index, len);//截出子串
            if (s3.length() > 1 && s3.charAt(0) == '0') return;

            Integer num = Integer.parseInt(s3);
            if (num > 255 || num < 0) return;
            sb.append(s3);
            ans.add(sb.toString());//符合条件则保存
        } else {
            for (int i = 0; i < 3; i++) {
                if (index + i + 1 < len) {
                    String s1 = s.substring(index, index + i + 1);
                    if (s1.length() > 1 && s1.charAt(0) == '0') continue;
                    Integer num = Integer.parseInt(s1);
                    if (num > 255 || num < 0) continue;
                    int len_sb = sb.length();
                    sb.append(s1).append('.');
                    dfs(s, sb, index + i + 1, site + 1, ans);
                    if (sb.length() > len_sb)
                        sb.delete(len_sb, sb.length());
                }
            }
        }

    }
}


